class Solution {//leetcode23——合并k个升序链表
private:
    ListNode* merge_sort(vector<ListNode*>& lists,int begin,int end){
        if(begin>end) return nullptr;
        if(begin==end) return lists[begin];
        //分治
        int mid=(begin+end)/2;
        ListNode* l1=merge_sort(lists,begin,mid);
        ListNode* l2=merge_sort(lists,mid+1,end);
        //归并排序
        return combine2list(l1,l2);
    };
    ListNode* combine2list(ListNode*l1,ListNode*l2){//合并两个有序链表
        ListNode newhead;
        ListNode* cur1=l1;
        ListNode* cur2=l2;
        ListNode* tail=&newhead;
        while(cur1&&cur2){
            if(cur1->val<cur2->val){
                tail->next=cur1;
                cur1=cur1->next;
            }
            else{
                tail->next=cur2;
                cur2=cur2->next;
            }
            tail=tail->next;
        }
        if(cur1) tail->next=cur1;
        if(cur2) tail->next=cur2;

        return newhead.next;
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //归并排序
        return merge_sort(lists,0,lists.size()-1);
    }
};